package ljl.alg.jianzhioffer.round3.easy;

public class _40_getLeastNumbers {

    public int[] getLeastNumbers(int[] arr, int k) {
        quick(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    void quick(int[] arr, int from, int to, int k) {
        if (from >= to)
            return;
        int l = from;
        int r = to;
        int pivot = arr[from];
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        if (l == k - 1) {
            return;
        }
        if (l > k - 1)
            quick(arr, from, l - 1, k);
        else
            quick(arr, l + 1, to, k);
    }
}
